<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    // 封装双向链表
    function DoublyLinkedList () {
      // 内部类: 节点类
      function Node(data) {
        this.data = data
        this.prev = null
        this.next = null
      }

      // 属性
      this.head = null
      this.tail = null
      this.length = 0

      // 1. append方法
      DoublyLinkedList.prototype.append = function (data) {
        var newNode = new Node(data)

        // 判断链表是否为空
        if (this.head == null) {
          this.head = newNode
          this.tail = newNode
        } else {
          this.tail.next = newNode
          newNode.prev = this.tail
          this.tail = newNode
        }

        // length + 1
        this.length += 1
      }

      // 2. 将链表转成字符串形式
      // 2.1 toString方法
      DoublyLinkedList.prototype.toString = function () {
        return this.backwardString()
      }

      // 2.2 forwardString方法
      DoublyLinkedList.prototype.forwardString = function () {
        // 定义变量
        var current = this.tail
        var resultString = ''

        // 依次向前遍历 获取每一个节点
        while (current) {
          resultString += current.data + ' '
          current = current.prev
        }
        return resultString
      }

      // 2.3 backwardString方法
      DoublyLinkedList.prototype.backwardString = function () {
        // 定义变量
        var current = this.head
        var resultString = ''

        // 依次向后遍历 获取每一个节点
        while (current) {
          resultString += current.data + ' '
          current = current.next
        }
        return resultString
      }

      // 3. insert方法
      DoublyLinkedList.prototype.insert = function (position, data) {
        // 越界判断
        if (position < 0 || position > this.length) return false

        // 根据data创建新的节点
        var newNode = new Node(data)

        // 判断原来的链表是否为空
        if (this.length == 0) {
          this.head = newNode
          this.tail = newNode
        } else {
          if (position == 0) { // 判断position是否为0
            this.head.prev = newNode
            newNode.next = this.head
            this.head = newNode
          } else if (position == this.length) {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
          } else {
            var current = this.head
            var index = 0
            while (index++ < position) {
              current = current.next
            }

            // 修改指针
            newNode.next = current
            newNode.prev = current.prev
            current.prev.next = newNode
            current.prev = newNode
          }
        }

        // length + 1
        this.length += 1
        return true
      }

      // 4. get方法
      DoublyLinkedList.prototype.get = function (position) {
        // 越界判断
        if (position < 0 || position >= this.length) return null

        // 获取元素
        var current = this.head
        var index = 0

        while (index++ < position) {
          current = current.next
        }

        return current.data
      }

      // 5. indexOf方法
      DoublyLinkedList.prototype.indexOf = function (data) {
        // 定义变量
        var current = this.head
        var index = 0

        // 查找和data相同的节点
        while (current) {
          if (current.data == data) {
            return index
          }
          current = current.next
          index += 1
        }

        return -1
      }

      // 6. update方法
      DoublyLinkedList.prototype.update = function (position, newData) {
        // 越界判断
        if (position < 0 || position >= this.length) return false

        // 寻找正确的节点
        var current = this.head
        var index = 0
        while (index++ < position) {
          current = current.next
        }

        // 修改找到节点的data信息
        current.data = newData
      }

      // 7. removeAt方法
      DoublyLinkedList.prototype.removeAt = function (position) {
        // 越界判断
        if (position < 0 || position >= this.length) return null

        // 判断是否只有一个节点
        var current = this.head
        if (this.length == 1) {
          this.head = null
          this.tail = null
        } else {
          if (position == 0) { // 判断是否删除的是第一个节点
            this.head.next.prev = null
            this.head = this.head.next
          } else if (position == this.length - 1) { // 最后节点
            current = this.tail
            this.tail.prev.next = null
            this.tail = this.tail.prev
          } else {
            var index = 0

            while (index++ < position) {
              current = current.next
            }

            current.prev.next = current.next
            current.next.prev = current.prev
          }
        }

        // length - 1
        this.length -= 1
        return current.data
      }

      // 8. remove方法
      DoublyLinkedList.prototype.remove = function (data) {
        // 根据data获取下标值
        var index = this.indexOf(data)

        // 根据index删除对应位置的节点
        return this.removeAt(index)
      }

      // 9. isEmpty方法
      DoublyLinkedList.prototype.isEmpty = function () {
        return this.length == 0
      }

      // 10. size方法
      DoublyLinkedList.prototype.size = function () {
        return this.length
      }

      // 11. 获取链表的第一个元素
      DoublyLinkedList.prototype.getHead = function () {
        return this.head.data
      }

      // 12. 获取链表的最后一个元素
      DoublyLinkedList.prototype.getTail = function () {
        return this.tail.data
      }

    }
    // 测试代码
    // 1. 创建LinkedList
    var list = new DoublyLinkedList()

    // 2. 测试append方法
    list.append('a')    
    list.append('b')
    list.append('c')
    alert(list)
    // alert(list.backwardString())
    // alert(list.forwardString())

    // 3. 测试insert方法
    // list.insert(1, '1')
    // list.insert(3, '2')
    // list.insert(5, '3')
    // alert(list)

    // 4. 测试get方法
    // alert(list.get(2))

    // 5. 测试indexOf方法
    // alert(list.indexOf('c'))

    // 6. 测试update方法
    // list.update(2, 'w')
    // alert(list)

    // 7. 测试removeAt方法
    // list.removeAt(1)
    // alert(list)

    // 8. 测试remove方法
    // list.remove('b')
    // alert(list)

    // 9. 测试其它方法
    // alert(list.isEmpty())
    // alert(list.size())
    // alert(list.getHead())
    // alert(list.getTail())
    

  </script>
</body>
</html>